Technical Field
This disclosure relates to techniques for determining where each of multiple mobile defense resources should be located to optimize the ability of the mobile defense resources to protect multiple mobile targets from an attack.
Description of Related Art
Stackelberg games have been widely applied to security domains, although most of this work has considered static targets, see Korzhyk, D., Conitzer, V., & Parr, R. (2010), “Complexity of computing optimal Stackelberg strategies in security resource allocation games,” In Proceedings of the 24th National Conference on Artificial Intelligence (AAAI), pp. 805-810; Krause, A., Roper, A., & Golovin, D. (2011), “Randomized sensing in adversarial environments,” In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2133-2139; Letchford, J., & Vorobeychik, Y. (2012), “Computing optimal security strategies for interdependent assets,” In The Conference on Uncertainty in Artificial Intelligence (UAI), pp. 459-468; Kiekintveld, C., Islam, T., & Kreinovich, V. (2013), “Security games with interval uncertainty,” In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS '13, pp. 231-238. Even when the players are mobile, e.g., in hider-seeker games, see Halvorson, E., Conitzer, V., & Parr, R. (2009), “Multi-step Multi-sensor Hider-Seeker Games,” In IJCAI, infiltration games, see Alpern, S. (1992), “Infiltration Games on Arbitrary Graphs,” Journal of Mathematical Analysis and Applications, 163, 286-288, or search games, see Gal, S. (1980), “Search Games,” Academic Press, New York, the models have considered static targets if any. Additionally, even when the targets were mobile, e.g., trains, see Yin, Z., Jiang, A. X., Johnson, M. P., Kiekintveld, C., Leyton-Brown, K., Sandholm, T., Tambe, M., & Sullivan, J. P. (2012), “TRUSTS: Scheduling randomized patrols for fare inspection in transit systems,” In Proceedings of the Twenty-Fourth Conference on Innovative Applications of Artificial Intelligence (IAN), pp. 2348-2355, the players were restricted to move along the targets to protect or attack them (the targets there are in essence stationary). Thus, these models may not be applicable to the problem with mobile resources and moving targets.
With respect to related work computing defender strategies for patrolling domains, see Agmon, N., Kraus, S., & Kaminka, G. A. (2008), “Multi-robot perimeter patrol in adversarial settings,” In IEEE International Conference on Robotics and Automation (ICRA), pp. 2339-2345, compute strategies for setting up a perimeter patrol in adversarial settings with mobile patrollers. Similarly, Basilico, N., Gatti, N., & Amigoni, F. (2009), “Leader-follower strategies for robotic patrolling in environments with arbitrary topologies,” In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)—Volume 1, pp. 57-64, compute the leader-follower equilibrium for robotic patrolling in environments with arbitrary topologies. In the same way, M. P. Johnson, F. Fang, and M. Tambe, “Patrol strategies to maximize pristine forest area,” In AAAI, 2012, propose a continuous game model for protecting forests from illegal logging. However, the targets are stationary in all this related work and may not fit the moving targets problem.
Bosansky, B., Lisy, V., Jakob, M., & Pechoucek, M. (2011), “Computing time-dependent policies for patrolling games with mobile targets,” In The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)—Volume 3, pp. 989-996 and Vanek, O., Jakob, M., Hrstka, O., & Pechoucek, M. (2011), “Using multi-agent simulation to improve the security of maritime transit,” In Proceedings of 12th International Workshop on Multi-Agent-Based Simulation (MABS), pp. 1-16, studied the problem of protecting moving targets. However, they both considered a model in which the defender, the attacker and targets have discretized movements on a directed graph. Such discretization of attacker strategy spaces may introduce sub-optimality in the solutions when attacker is allowed to choose strategy from a continuous strategy space. Furthermore, Bosansky et al. (see, Bosansky, B., Lisy, V., Jakob, M., & Pechoucek, M. (2011), “Computing time-dependent policies for patrolling games with mobile targets,” In The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)—Volume 3, pp. 989-996) presented a formulation with non-linear constraints, which may face scaling problems even with a single defender resource.